/* 3.求子数组的最大和（数组）
 * 题目：
 * 输入一个整形数组，数组里有正数也有负数。
 * 数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
 * 求所有子数组的和的最大值。要求时间复杂度为O(n)。
 *
 * 例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10,
 * -4, 7, 2，因此输出为该子数组的和18。
 */

/* ANSWER:
 * A traditional greedy approach.
 * Keep current sum, slide from left to right, when sum < 0, reset sum to 0;
 */
#include <stdio.h>

int max_sub_array1(int **pb, int **pe);
/* int max_sub_array(int a[], int size); */

int main()
{
  int a[] = {1, -2, 3, 10, -4, 7, 2, -5};
  int max;
  int *pb = a;
  int *pe = a+8;
  int *ptr;
  //max = max_sub_array(a, 8);
  printf("The original array is:");
  for (ptr = pb; ptr < pe; ptr++)
    printf(" %d", *ptr);
  printf("\n");
  
  max = max_sub_array1(&pb, &pe);
  printf("max subarray is %d\n", max);

  printf("The subarray is:");
  for (ptr = pb; ptr < pe; ptr++) {
    printf(" %d", *ptr);
  }

  printf("\n");
  
  return 0;
}

int max_sub_array1(int **pb, int **pe) {
  int sum = 0;
  int max = - (1 << 31); /* make sure max is initialed small enough */
  int* pcur = *pb;
  int* pend = *pe;
  
  if (*pb >= *pe ) perror("error array size");

  while (pcur < pend) {
    sum += *pcur++;
    if (sum > max) {
      max = sum;
      *pe = pcur;
    } else if (sum < 0) {
      sum = 0;
      *pb = pcur;
    }
  }

  return max;
}

int max_sub_array(int a[], int size) {
  int sum = 0;
  int max = - (1 << 31);
  int cur = 0;
  
  if (size <= 0) perror("error array size");

  while (cur < size) {
    sum += a[cur++];
    if (sum > max) {
      max = sum;
    } else if (sum < 0) {
      sum = 0;
    }
  }

  return max;
}
